package com.study.lihan.letcode;
/*给你一个字符串 s，找到 s 中最长的回文子串。
https://leetcode-cn.com/problems/longest-palindromic-substring/
示例 1：

输入：s = "babad"
输出："bab"
* */
public class My5 {
    static  String s = "aaaa";
    public static void main(String[] args) {
          String result = coreExplan(s);
        System.out.println("结果是："+result);
    }

    public static  String mylongestPalindrome(String s) {
           String result ="";
        if(s ==null || s.length()==0)return "";
        int strLen = s.length();
        for(int i = 0; i<strLen; i++){

        }

     return result;
    }

//动态规划
    public static String dynamicPlan(String s){
        int startIndex = 0;
        int maxLen = 1;
        if(s ==null) return  "";
        char[] charArr = s.toCharArray();
        int strLen = charArr.length;
        boolean[][] dp = new boolean[strLen][strLen];

        for(int i=0; i< strLen; i++){
            dp[i][i] = true;
        }

        for(int len =2; len<=strLen; len++){
            for(int index=0; index+len<=strLen;index++ ){
                int end= index+len-1;
                if(charArr[index] != charArr[end])continue;
                if( len>2 && !dp[index+1][index+len-2])continue;;
                maxLen = len;
                startIndex = index;
                dp[index][end]=true;
            }

        }
        return  s.substring(startIndex,maxLen+startIndex);
    }

//中心扩展
    public static String  coreExplan(String s){
        int startIndex = 0;
        int maxLen = 1;
        if(s ==null || s.length()==0)return "";
        int strLen = s.length();
        for(int i = 0; i<strLen; i++){
            int len1= expandAroundCenter(s,i,i);
            int len2= expandAroundCenter(s,i,i+1);
            int len = Math.max(len1,len2);
            if(len <= maxLen)continue;
            maxLen = len;
            if(maxLen%2==0){
                startIndex = i-maxLen/2+1;
            }else{
                startIndex = i-maxLen/2;
            }

        }

        return s.substring(startIndex,startIndex+maxLen);
    }
    public  static int expandAroundCenter(String s,int left, int right){
        int strLen = s.length();
        //考虑到中心扩展的元素是一个还是两个
        if(right>=strLen || s.charAt(left)!= s.charAt(right)) return 0;
        int offset = 0;
        for(; left-offset>=0 && right+offset <strLen; offset++ ){
            char rightChar = s.charAt(right+offset);
            char leftChar = s.charAt(left-offset);
            if(rightChar != leftChar)break;
        }
        return right-left+offset*2-1;
    }





}
